1. Field of the Invention
The present invention relates generally to data communication and, more particularly, to systems and methods for performing random early detection (RED) in a data forwarding sub-system.
2. Description of Related Art
Network devices, such as routers, relay streams of data through a network from a source to a destination. Typically, the network devices include one or more memory subsystems to temporarily buffer data before transferring the data from the device. A network device may assign a number of queues (e.g., where a queue may be considered a logical first-in, first-out (FIFO) buffer) with which to buffer the data. In some instances, queues may be associated with characteristics of the data, such as destination interfaces (e.g., ports) of the data and/or a “class” of the data or some other combination of characteristics.
In some situations, data may build up too quickly in the queues (i.e., data is enqueued at a faster rate than it is dequeued), thereby causing congestion. To avoid forced “tail dropping” (i.e., dropping a chunk (e.g., a packet) of data from the tail of a queue, or before it is added to the queue), network devices may proactively employ RED to randomly drop chunks of data and ease congestion in the queues. RED schemes typically involve fixed-size queues in which fixed threshold values determine when chunks of data are randomly dropped and with what probabilities.
Some network devices, however, may dynamically adjust queue sizes in accordance with current usage conditions. Such dynamic adjustment of queue size may, for example, enforce fairness when resources are scarce within the network device and promote sharing when resources are plentiful. Each one of dynamic adjustment of queue size and RED is challenging to implement alone, and such difficulties would be multiplied if RED were desired in a changing queue environment. Different classes (e.g., service levels) of data only add to these problems.
As a result, there is a need for systems and methods for implementing RED in an environment where queue sizes/lengths dynamically change.